#include<cstdio>//uncle-lu
#include<algorithm>
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }
	while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	x = f ? -x : x;
	return ;
}

int n, m, cnt;
int v[70][4], p[70][4];
int F[40010], line[70];

int main()
{
	read(n); read(m);
	int a, b, c;
	for (int i = 1; i <= m; i++) 
	{
		read(a);read(b);read(c);
		if(c == 0)
		{
			++cnt;
			v[cnt][1] = a;
			p[cnt][1] = b * a;
			line[i] = cnt;
		}
		else
		{
			c = line[c];
			v[c][0]++; p[c][0]++;
			v[c][ v[c][0] + 1 ] = a;
			p[c][ p[c][0] + 1 ] = b * a;
		}
	}

	for (int i = 1; i <= cnt; i++) 
	{
		if(v[i][0] == 0)
		{
			for (int j = n; j >= v[i][1]; j--) 
				F[j] = std::max(F[j], F[j-v[i][1]] + p[i][1] );
		}
		if(v[i][0] == 1)
		{
			for (int j = n; j >= 1; j--) 
			{
				if(j >= v[i][1])F[j] = std::max(F[j], F[j-v[i][1]] + p[i][1] );
				if(j >= v[i][1] + v[i][2])F[j] = std::max(F[j], F[ j - v[i][1] - v[i][2] ] + p[i][1] + p[i][2] );
			}
		}
		if(v[i][0] == 2)
		{
			for (int j = n; j >= 1; j--) 
			{
				if(j >= v[i][1])F[j] = std::max(F[j], F[j-v[i][1]] + p[i][1] );
				if(j >= v[i][1] + v[i][2])F[j] = std::max(F[j], F[ j - v[i][1] - v[i][2] ] + p[i][1] + p[i][2] );
				if(j >= v[i][1] + v[i][3])F[j] = std::max(F[j], F[ j - v[i][1] - v[i][3] ] + p[i][1] + p[i][3] );
				if(j >= v[i][1] + v[i][2] + v[i][3])F[j] = std::max(F[j], F[ j - v[i][1] - v[i][2] - v[i][3] ] + p[i][1] + p[i][2] + p[i][3]);
			}
		}
	}

	printf("%d", F[n]);
	return 0;
}
